/**
 * https://leetcode-cn.com/problems/linked-list-cycle-ii/
 * 环形链表II
 * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
 * @param head 
 */
 const detectCycle = (head: ListNode | null): ListNode | null => {
    // 边界判断
    if (head === null) return null

    let slow: ListNode = head, 
        fast: ListNode | null = head;

    while (fast !== null) {
        slow = slow.next!; // 慢指针走一步
        if (fast.next !== null) {
            // 快指针走两步
            fast = fast.next.next;
        } else {
            // 不是环形链表, 不存在环状入口
            return null
        }

        // 快慢指针相遇了
        if (fast === slow) {
            // 头指针, 指向头
            let p = head;

            // 等头尾相遇的时候时, 就是环状入口点
            while (p !== slow) {
                p = p.next!;
                slow = slow.next!
            }
            return p
        }
    }

    return null
};


const detectCycle2 = (head: ListNode | null): ListNode | null => {
    // 边界判断
    if (head === null) return null

    const map: WeakMap<ListNode, ListNode> = new WeakMap()

    while (head !== null) {
        // 找到了入口的节点
        if (map.get(head)) return head;
        map.set(head, head)
        head = head.next;
    }

    return null
};